package com.lans.binary;

/**
 * @author: lans
 * @date: 2025/2/28
 * @name: 刘宇
 */
public class Heap <T extends Comparable<T>> {
    //实现堆的数组
    private T[] items;

    //记录堆的大小
    private int N;

    public Heap(int capacity){
        items = (T[])new Comparable[capacity+1];//N即代表最大索引
        N=0;
    }

    //判断索引 i 除的元素与接触的元素的大小关系
    //判断 i处的元素是否 小于 j处的元素
    public boolean less(int i, int j){
        return items[i].compareTo(items[j]) < 0;
    }

    //交换i和j处的元素
    public void exch(int i, int j){
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    //k等于是新加入的节点索引
    //上浮算法
    public void swim(int k){
        //当k=1时说明已经到达根节点
        //0与1无需比较
        while(k>1){
            if(less(k/2,k)){//说明父节点小于子节点
                exch(k/2,k);
            }
            k=k/2;
        }
    }

    //平衡删除后的堆结构 k是索引
    public void sink(int k){
        //找到子节点中的最大值
        while(k*2<=N){
            int max;
            if(2*k+1<=N){//存在右节点
                if(less(2*k,2*k+1)){//比较左是否小于右
                     max = 2 * k + 1;
                }else{
                    max = 2*k;
                }
            }else{//不存在最大即假设为左节点
                max = 2*k;
            }
            //当前节点比左右子节点还大则不需要交换位置 结束循环即可
            if(!less(k,max)){
                break;
            }
            //当前节点小于最大值则交换位置
            exch(k,max);
            k=max;
        }
    }

    //删除堆中的最大元素 根节点
    public T delMax(){
        T max = items[1];
        exch(1,N);
        items[N--]=null;//删除最大
        //调整删除后的平衡位置
        sink(1);
        return max;
    }

    //新增
    public void insert(T value){
        this.items[++N]=value;
        //新增的数进行上浮
        swim(N);
    }
}